package test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/**
 * @author sunzhuokun
 * @date 15:01 2024/5/10
 * @description 整数对最小和
 * 给定两个整数数组 array1 array2
 * 数组元素按升序排列
 * 假设从array1 array2中分别取出一个元素可构成一对元素
 * 现在需要取出K个元素
 * 并对取出的所有元素求和
 * 计算和的最小值
 * 注意：
 * 两对元素如果对应于array1 array2中的两个下标均相同，则视为同一个元素
 * 输入描述
 * <p>
 * 输入两行数组array1 array2
 * 每行首个数字为数组大小 size( 0 < size <= 100)
 * array1，array2中的每个元素e， 0< e <1000
 * 接下来一行为正整数k (0 < k <= array1.size() * array2.size())
 * 输出描述
 * <p>
 * 满足要求的最小和
 * <p>
 * 说明
 * <p>
 * 输入
 * 3 1 1 2
 * 3 1 2 3
 * 2
 * 输出
 * 4
 * 用例中，需要取两个元素 取第一个数组第0个元素 与第二个数组第0个元素，组成一对元素[1,1]
 * 取第一个数组第1个元素 与第二个数组第0个元素，组成一对元素[1,1]
 * 求和为1+1+1+1=4 为满足要求的最小和
 */
public class IntegerPairMinSum_整数对最小和 {

    /**
     * 这道题可以看做是两个有序数组的归并排序的变形。先将两个数组中的元素两两相加，得到 m×n 个元素，将这些元素按和的大小升序排序。题目要求取出前 k 个元素的和的最小值。
     * 因为数组是有序的，可以考虑使用双指针法，用两个指针 i 和 j 分别指向数组 A 和数组 B，从头开始依次枚举每个元素，记录当前已经选取的元素个数
     * cnt。每次选取两个指针指向的元素中较小的一个，将其加入答案中，并将所在数组的指针向后移动一位。当 cnt 达到 k 时停止。
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int[] arr1 = new int[m];
        for (int i = 0; i < m; i++) {
            arr1[i] = scan.nextInt();
        }
        int n = scan.nextInt();
        int[] arr2 = new int[n];
        for (int i = 0; i < n; i++) {
            arr2[i] = scan.nextInt();
        }

        int k = scan.nextInt();

        Node[] nodes = new Node[m * n];
        int nodeLen = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                nodes[nodeLen++] = new Node(i, j, arr1[i] + arr2[j]);
            }
        }

        Arrays.sort(nodes, 0, nodeLen, Comparator.comparingInt(a -> a.val));

        int ans = 0;
        boolean[] visited = new boolean[m];
        int cnt = 0;
        for (int i = 0; i < nodeLen; i++) {
            if (visited[nodes[i].i]) {
                continue;
            }
            ans += nodes[i].val;
            visited[nodes[i].i] = true;
            cnt++;
            if (cnt == k) {
                break;
            }
        }
        System.out.println(ans);
    }

    static class Node {
        int i, j, val;

        public Node(int i, int j, int val) {
            this.i = i;
            this.j = j;
            this.val = val;
        }
    }
}
